题目描述

原题

Description:
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0?
Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

原题翻译

描述:
给定一个包含n个实数的数组nums，其中是否存在元素a，b，c，使得a + b + c = 0？
找到数组中所有唯一的三元组，它们的总和为零。

另外:

结果集中不得包含重复的三元组

例如:

给定数组 nums = [-1, 0, 1, 2, -1, -4],
一个解决方案集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

解法一

主要思想

首先，对数组进行排序。

然后，从0位置开始到倒数第三个位置（num.length-3)，进行遍历，假定num[i]就是3sum中得第一个加数，然后从i+1的位置开始，进行2sum的运算。

当找到一个3sum==0的情况时，判断是否在结果hashset中出现过，没有则添加。(利用hashset的value唯一性）

因为结果不唯一，此时不能停止，继续搜索，左右指针同时挪动。

需要注意：

  1. 排除一切结果为空的情况。

  2. 若第一次遍历到的值大于0，则后续一定也大于0。

  3. 若第一次遍历到的值等于0，则只需判断后面有没有两个相同值。

运行速度：超过了91.74%的解答。

内存使用：超过了91.87%的解答。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums.length < 3 || nums == null)
            return res;
        Arrays.sort(nums); // 对数组排序
	    if (nums[0] > 0 || nums[nums.length - 1] < 0) { // 若数组中，最小值大于0 或 最大值小于0，则直接返回res。
	        return res;
        }
        for (int i = 0; i <= nums.length - 3; i++) {
            if (nums[i] > 0) { // 若nums[i]的3倍比目标值大，后面的结果一定小
                break;
            }
            if (nums[i] == 0) { // 若nums[i]的3倍与目标值相等
                if (nums[i + 1] == 0 && nums[i + 2] == 0) {
                        List<Integer> unit = new ArrayList<Integer>();
                        unit.add(0);
                        unit.add(0);
                        unit.add(0);
                        res.add(unit);
                }
                break;
            }
            if (i == 0 || nums[i] != nums[i-1]) { // 避免重复
                int low = i + 1;
                int high = nums.length - 1;
                while (low < high) {
                    int sum = nums[i] + nums[low] + nums[high];
                    if (sum == 0) {
                        List<Integer> unit = new ArrayList<Integer>();
                        unit.add(nums[i]);
                        unit.add(nums[low]);
                        unit.add(nums[high]);
                        res.add(unit);
                        low++;
                        high--;
                        while (low < high && nums[low] == nums[low - 1]) // 避免重复
                            low++;
                        while (low < high && nums[high] == nums[high + 1]) // 避免重复
                            high--;
                    } else if (sum > 0)
                        high--;
                    else {
                        low++;
                    }
                }
            }
        }
        return res;
    }
}